Maximum Order of Triangle‐Free Graphs with a Given Rank

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle‐free graphs with a given rank and characterize all such graphs achieving the maximum order.     

The reduced expressions in a Coxeter system with a strictly complete Coxeter graph

Let (W,S)$(W,S)$ be a Coxeter system with a strictly complete Coxeter graph. The present paper concerns the set Red(z)$\mathrm{Red}(z)$ of all reduced expressions for any z∈W$z\in W$. By associating each bc-expression to a certain symbol, we describe the set Red(z)$\mathrm{Red}(z)$ and compute its cardinal |Red(z)|$|\mathrm{Red}(z)|$ in terms of symbols. An explicit formula for |Red(z)|$|\mathrm{Red}(z)|$ is deduced, where the Fibonacci numbers play a crucial role.     

Cycle-maximal triangle-free graphs

We conjecture that the balanced complete bipartite graph _{K⌊n/2⌋,⌈n/2⌉}$K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$ contains more cycles than any other n$n$-vertex triangle-free graph, and we make some progress toward proving this. We give equivalent conditions for cycle-maximal triangle-free graphs; show bounds on the numbers of cycles in graphs depending on numbers of vertices and edges, girth, and homomorphisms to small fixed graphs; and use the bounds to show that among regular graphs, the conjecture holds. We also consider graphs that are close to being regular, with the minimum and maximum degrees differing by at most a positive integer k$k$. For k=1$k=1$, we show that any such counterexamples have n≤91$n\le 91$ and are not homomorphic to _C5$C_5$; and for any fixed k$k$ there exists a finite upper bound on the number of vertices in a counterexample. Finally, we describe an algorithm for efficiently computing the matrix permanent (a #P$\#P$-complete problem in general) in a special case used by our bounds.     

A Complete Solution to Spectrum Problem for Five‐Vertex Graphs with Application to Traffic Grooming in Optical Networks

A G‐design of order n is a decomposition of the complete graph on n vertices into edge‐disjoint subgraphs isomorphic to G. Grooming uniform all‐to‐all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph on n vertices into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The existence spectrum problem of G‐designs for five‐vertex graphs is a long standing problem posed by Bermond, Huang, Rosa and Sotteau in 1980, which is closely related to traffic groomings in optical networks. Although considerable progress has been made over the past 30 years, the existence problems for such G‐designs and their related traffic groomings in optical networks are far from complete. In this paper, we first give a complete solution to this spectrum problem for five‐vertex graphs by eliminating all the undetermined possible exceptions. Then, we determine almost completely the minimum drop cost of 8‐groomings for all orders n by reducing the 37 possible exceptions to 8. Finally, we show the minimum possible drop cost of 9‐groomings for all orders n is realizable with 14 exceptions and 12 possible exceptions.     

Perfect 1‐Factorizations of a Family of Cayley Graphs

A 1‐factorization of a graph G is a decomposition of G into edge‐disjoint 1‐factors (perfect matchings), and a perfect 1‐factorization is a 1‐factorization in which the union of any two of the 1‐factors is a Hamilton cycle. We consider the problem of the existence of perfect 1‐factorizations of even order 4‐regular Cayley graphs, with a particular interest in circulant graphs. In this paper, we study a new family of graphs, denoted , which are Cayley graphs if and only if k is even or . By solving the perfect 1‐factorization problem for a large class of graphs, we obtain a new class of 4‐regular bipartite circulant graphs that do not have a perfect 1‐factorization, answering a problem posed in 7 . With further study of graphs, we prove the nonexistence of P1Fs in a class of 4‐regular non‐bipartite circulant graphs, which is further support for a conjecture made in 7 .     

Optimal Groomings with Grooming Ratios Six and Seven

Grooming uniform all‐to‐all traffic in optical (SONET) rings with grooming ratio C requires the determination of a decomposition of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The determination of optimal C‐groomings has been considered for , and completely solved for . For , it has been shown that the lower bound for the drop cost of an optimal C‐grooming can be attained for almost all orders with 5 exceptions and 308 possible exceptions. For , there are infinitely many unsettled orders; especially the case is far from complete. In this paper, we show that the lower bound for the drop cost of a 6‐grooming can be attained for almost all orders by reducing the 308 possible exceptions to 3, and that the lower bound for the drop cost of a 7‐grooming can be attained for almost all orders with seven exceptions and 16 possible exceptions. Moreover, for the unsettled orders, we give upper bounds for the minimum drop costs.     

Matching energy of unicyclic and bicyclic graphs with a given diameter

Gutman and Wagner proposed the concept of matching energy (ME) and pointed out that the chemical applications of ME go back to the 1970s. Let G be a simple graph of order n and be the roots of its matching polynomial. The ME of G is defined to be the sum of the absolute values of . In this article, we characterize the graphs with minimal ME among all unicyclic and bicyclic graphs with a given diameter d. © 2014 Wiley Periodicals, Inc. Complexity 21: 224–238, 2015     

An infinite family of subcubic graphs with unbounded packing chromatic number

Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number.